#include <iostream>
#include <vector>
#include <string>
using namespace std;

//void getPrefix(vector<int>& prefix, const string& str)
//{
//	if (str.size() == 0)
//		return;
//	int j = 0;
//	prefix[0] = 0;
//	for (int i = 1; i < str.size(); i++)
//	{
//		while (j > 0 && str[i] != str[j])
//		{
//			j = prefix[j];
//		}
//
//		if (str[i] == str[j])
//			j++;
//
//		prefix[i] = j;
//	}
//}
//
//const char* Strstr(const char* str, const char* strSearch)
//{
//	int m = strlen(str), n = strlen(strSearch);
//	string s = str;
//	vector<int> prefix(n);
//	getPrefix(prefix, strSearch);
//
//	int j = 0;
//	int i = 0;
//	while (i < m)
//	{
//		if (j == n)
//		{
//			return strSearch;
//		}
//
//		if (str[i] != strSearch[j])
//		{
//			if (j > 0)
//				j = prefix[j - 1];
//			else
//				j = 0;
//		}
//		else
//		{
//			j++;
//		}
//
//		i++;
//	}
//	if (j == n)
//		return strSearch;
//	else 
//		return nullptr;
//}

int findNumber(vector<int> arr, int target)
{
	int l = 0, r = arr.size() - 1;

	while (l < r)
	{
		int mid = (l + r + 1) / 2;
		if (arr[mid] > arr[arr.size() - 1])
		{
			l = mid;
		}
		else
		{
			r = mid - 1;
		}
	}
	int left = l + 1, right = arr.size() - 1;
	if (target > arr.size() - 1)
	{
		left = 0;
		right = l;
	}
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (target == arr[mid])
		{
			return mid;
		}
		else if (target > arr[mid])
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}

	return -1;
}

int main()
{
	vector<int> arr = { 5, 6, 7, 8 ,9 ,1,2,3,4 };
	cout << findNumber(arr, 10) << endl;
	return 0;
}

//int main()
//{
//
//
//	//const char* ret = Strstr("abctxtedefgtx", "txte");
//	//if (ret)
//	//	cout << ret << endl;
//	//else
//	//	cout << "nullptr" << endl;
//
//	return 0;
//}

//int fib(int n)
//{
//	if (n == 1 || n == 2)
//		return 1;
//	else 
//		return fib(n - 1) + fib(n - 2);
//}
//
//int fibNonR(int n)
//{
//	if (n == 1 || n == 2)
//		return 1;
//	int a = 1, b = 1;
//	n -= 2;
//	while (n--)
//	{
//		int z = a + b;
//		a = b;
//		b = z;
//	}
//
//	return b;
//}
//
//int main()
//{
//	cout << fib(30) << endl;
//	cout << fibNonR(30) << endl;
//	return 0;
//}